#include <map>
#include <vector>
#include "heap.h"

using namespace std;

template<class T>
const T* heap<T>::top() const {
  return &(heap_[0]);
}

template<class T> 
T heap<T>::pop() {
  T returnable = heap_[0];
  remove(0);
  return returnable;
}

template<class T>
bool heap<T>::remove(const T& item) {
  typename map<T,int>::iterator it = index_.find(item);
  if (it == index_.end())
    return false;

  remove(it->second);
}

template<class T>
void heap<T>::insert(const T& item) {
  heap_.push_back(item);
  index_[item] = heap_.size() - 1;
  bubble_up(heap_.size() -1);
}

template<class T>
bool heap<T>::update(const T& old, const T& replacement) {
  typename map<T, int>::iterator it = index_.find(old);
  if (it == index_.end())
    return false;
  int pos = it->second;
  index_.erase(it);
  
  heap_[pos] = replacement;
  index_[replacement] = pos;
  bubble(pos);
}

template<class T>
bool heap<T>::remove(int pos) {
  swap(pos, heap_.size() - 1);
  index_.erase(heap_.back());
  heap_.pop_back();
  bubble_down(pos);
}

template<class T>
void heap<T>::bubble(int pos) {
  if (heap_[parent(pos)] < heap_[pos]) {
    bubble_up(pos);
  } else if (((left(pos) < heap_.size())
	      && (heap_[pos] < heap_[left(pos)])) || 
	     ((right(pos) < heap_.size())
	      && (heap_[pos] < heap_[right(pos)]))) {
    bubble_down(pos);
  }
}

template<class T>
void heap<T>::bubble_up(int pos) {
  if (pos == 0)
    return;
  if (heap_[parent(pos)] < heap_[pos]) {
    swap(pos, parent(pos));
    bubble_up(parent(pos));
  }
}

template<class T>
void heap<T>::bubble_down(int pos) {
  if (is_leaf(pos))
    return;
  int max_child_pos = max_child(pos);
  if (heap_[pos] < heap_[max_child_pos]) {
    swap(pos, max_child_pos);
    bubble_down(max_child_pos);
  }
}
